package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * <h3>最长递增子序列 - 动态规划</h3>
 */
public class Leetcode300 {

    /**
     * 动态规划
     * 1   2   3   4
     * 1   3   6   4   9
     * 1   3   6   4   9
     * 13  16  14  19
     * 36  34  39
     * 136 134 139
     * 69
     * 169
     * 369
     * 1369
     * 49
     * 149
     * 349
     * 1349
     * (1) (2) (3) (3) (4)
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Integer.max(dp[i], dp[j] + 1);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    /**
     * <a href="https://leetcode.cn/problems/longest-increasing-subsequence/solutions/14796/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/">耐心排序讲解</a>
     *
     * @param nums
     * @return
     */
    public int patientSort(int[] nums) {
        int[] top = new int[nums.length]; // 最多分成 nums.length 堆 ，top数组是由每堆牌里最上面一张（也就是最小的一张）组成的
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0;
            int right = piles;
            // top 是有序的，升序
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if (left == piles) {
                piles++;
            }
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }

    public static void main(String[] args) {
        Leetcode300 code = new Leetcode300();
        System.out.println(code.lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
        System.out.println(code.patientSort(new int[]{1, 3, 6, 4, 9}));
    }
}